// https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

// 题干：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
//       给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

// 示例：输入：digits = "23"
//       输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

// 碎语：本题先设置一个字典来记录各个数字可能代表的字母
//       各个数字代表的字母各不相同，不存在重复(剪枝)问题，回溯的时候撤销该操作即可
//       所谓设立一个字典，申请一个字符串数组即可

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    string hash[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> res;
    string path;
public:
    vector<string> letterCombinations(string digits)
    {
        if (digits.size() == 0) return {};

        dfs(digits, 0);
        return res;
    }

    void dfs(string& digits, int index)
    {
        if (index == digits.size()){
            res.push_back(path);
            return ;
        }

        // for循环的使用使代码更具有可读性，更美观
        for(auto ch : hash[digits[index] - '0'])
        {
            path.push_back(ch);
            dfs(digits, index + 1);
            path.pop_back(); // 恢复现场
        }
    }
};

int main()
{
    Solution sol;
    string digits = "23";

    vector<string> index = sol.letterCombinations(digits);
    for (const string& str : index){
        cout << str << endl;
    }

    return 0;
}